package QuestionDaily;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SmallestInfiniteSet {
    /**
     * 现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...]
     * 实现 SmallestInfiniteSet 类
     */
    /**
     * 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
     */
    public SmallestInfiniteSet() {
        /**
         * 无需真的含有所有整数
         * 只需要记录没有哪些元素即可
         * 134ms
         * 这么慢可能是由于remove操作
         */
        non=new ArrayList<>();
    }
    List<Integer>non;  //升序排列记录不包含的元素

    /**
     * 移除 并返回该无限集中的最小整数。
     */
    public int popSmallest() {
        int index=0;
        for(int i=1;i<=1000;i++){ //从小到大遍历
            if(index==non.size() || non.get(index++)!=i){  //如果该元素不存在non中，直接返回
                non.add(i);     //移除该元素
                Collections.sort(non);
                return i;
            }
        }
        return 0;
    }

    /**
     * 如果正整数 num 不 存在于无限集中，则将一个 num 添加 到该无限集中
     * @param num 1 <= num <= 1000
     */
    public void addBack(int num) {
        /**
         * 因为每次删除只能从最小值递增删除
         * 所以non是一个有序集合
         * 使用二分查找
         * 1，2，3 ......
         */
        if(non.size()==0)
            return;
        int l=0,r=non.size()-1;
        int mid=0;
        boolean flag=false;
        if (num <= non.get(r) && num >= non.get(l)) {
            while (l<=r) {
                mid = l + (r - l) / 2;
                if (num < non.get(mid))
                    r = mid - 1;
                else if(num == non.get(mid)){
                    flag=true;
                    break;
                }else
                    l = mid + 1;
            }
        }
        if(flag)non.remove(mid);
    }
}
